Tree DFS: Depth-First Search, a Traversal Method from Root to Leaf
A tree consists of nodes and edges, where each node (except the root) has exactly one parent and can have multiple children. Depth-First Search (DFS) is a traversal method that "goes deep into one path until it ends, then backtracks." Tree DFS traversals include pre-order (root → left → right), in-order, and post-order, with pre-order most directly reflecting root-to-leaf paths. For recursive pre-order traversal: visit the current node → recursively traverse the left subtree → recursively traverse the right subtree. Using the example tree (root 1, left child 2, right child 3; 2 has left child 4 and right child 5), the traversal order is 1 → 2 → 4 → 5 → 3. For non-recursive implementation, a stack is used: initialize with the root, then repeatedly pop the top node, visit it, and push its right child first followed by its left child onto the stack. Root-to-leaf DFS traversal is applied to problems like path sum calculation and path output. Recursive implementation is intuitive, while non-recursive stack-based methods are suitable for large datasets. Mastering pre-order traversal is a core skill for tree structure manipulation.
Read MoreBinary Trees: Three Traversal Methods of Binary Trees, Recursive Implementation Made Super Simple
This article introduces three classic traversal methods of binary trees (pre-order, in-order, and post-order), implemented recursively, with the core being clarifying the position of root node access. Each node in a binary tree has at most left and right subtrees. Traversal refers to visiting nodes in a specific order. Recursion is key here, similar to "matryoshka dolls," where the function calls itself with a narrowed scope until empty nodes are encountered, terminating the recursion. The differences between the three traversal orders are: - Pre-order: Root → Left → Right; - In-order: Left → Root → Right; - Post-order: Left → Right → Root. Using an example tree (root 1 with left child 2 and right child 3; node 2 has left child 4 and right child 5), the traversal results are: - Pre-order: 1 2 4 5 3; - In-order: 4 2 5 1 3; - Post-order: 4 5 2 3 1. The core of recursive implementation lies in the termination condition (returning for empty nodes) and recursively traversing left and right subtrees in the traversal order. By clarifying the root position and recursive logic, the traversal process can be clearly understood.
Read More